深度学习算法(第35期)----强化学习之马尔科夫决策过程
上期我们一起学习了强化学习中梯度策略的相关知识，
深度学习算法(第34期)----强化学习之梯度策略实现
今天我们学习强化学习中的马尔科夫决策过程的相关知识。
在二十世纪初，数学家 Andrey Markov 研究了没有记忆的随机过程，称为马尔可夫链。这样的过程具有固定数量的状态，并且在每一步中随机地从一个状态演化到另一个状态。它从状态S演变为状态S'的概率是固定的，它只依赖于(S, S')对，而不是依赖于过去的状态（系统没有记忆）。
下图显示了一个具有四个状态的马尔可夫链的例子。假设该过程从状态S0开始，并且在下一步骤中有 70% 的概率保持在该状态不变。最终，它必然离开那个状态，并且永远不会回来，因为没有其他状态能够回到S0。如果它进入状态S1，那么它很可能会进入状态S2（90% 的概率），然后立即回到状态S1（100% 的概率）。它可以在这两个状态之间交替多次，但最终它会落入状态S3并永远留在那里（这是一个终端状态）。马尔可夫链可以有非常不同的应用，它们在热力学、化学、统计学等方面有着广泛的应用。
20时间50年代，马尔科夫决策过程（MDP）由Richard Bellman首次提出，有点类似于马尔科夫链，在状态转移的每一步中，一个智能体可以选择几种可能的动作中的一个，并且转移概率取决于所选择的动作。此外，一些状态转移返回一些奖励（正或负），智能体的目标是找到一个策略，随着时间的推移将最大限度地提高奖励。
例如，下图中所示的MDP,在每个步骤中具有三个状态和最高三个可能的离散动作。如果从状态S0开始，随着时间的推移可以在动作a0、a1或a2之间进行选择。如果它选择动作a1，它就保持在状态S0中，并且没有任何奖励。因此，如果愿意的话，它可以决定永远呆在那里。但是，如果它选择动作a0，它有 70% 的概率获得 10 分的奖励，并保持在状态S0。然后，它可以一次又一次地尝试获得尽可能多的奖励。但它将在状态S1中结束这样的行为。在状态S1中，它只有两种可能的动作：a0或a2。它可以通过反复选择动作a1来选择停留，或者它可以选择动作a2移动到状态S2并得到 -50 分的 奖励。在状态S2中，只能选择采取行动S1，这将最有可能引导它回到状态S0，在途中获得 40 分的奖励。通过观察这个 MDP，你能猜出哪一个策略会随着时间的推移而获得最大的回报吗？在状态S0中，清楚地知道a0是最好的选择，在状态S2中，智能体别无选择，只能采取行动a1，但是在状态S1中，智能体否应该保持不动（a0）或通过火（a2），这是不明确的。
Bellman 找到了一种估计任何状态S最佳状态值的方法，就是利用智能体在其采取最佳行为达到状态s之后，所有未来衰减奖励总和的平均期望。他表明，如果智能体的行为最佳，那么对于所有的状态s可以利用如下公式：
。这个递归公式表示，如果智能体最优地运行，那么当前状态的最优值就等于在采取一个最优动作之后平均得到的奖励，加上该动作可能导致的所有可能的下一个状态的期望最优值。
其中：
T为智能体选择动作a时从状态s到状态s'的转移概率
R为智能体选择以动作a从状态s到状态s'的过程中得到的奖励
γ为衰减率
这个等式直接引出了一种算法，该算法可以精确估计每个可能状态的最优状态值：首先将所有状态值估计初始化为零，然后用数值迭代算法迭代更新它们：
其中，Vk(s)是在k次算法迭代对状态s的估计。显然，给定足够的时间，这些估计保证收敛到最优状态值，对应于最优策略。
了解最佳状态值很有用，特别是评估策略，但它没有明确地告诉智能体要做什么。幸运的是，Bellman 发现了一种非常类似的算法来估计最优状态-动作值（state-action values），通常称为 Q 值。状态行动(s, a)对的最优 Q 值，记为Q(s, a)，表示智能体在到达状态s，然后选择动作a之后未来平均衰减奖励的期望的总和。但是在它看到这个动作的结果之前，假设它在该动作之后的动作是最优的。
下面是它的工作原理：再次，通过初始化所有的 Q 值估计为零，然后使用 Q 值迭代算法更新它们，如下：
一旦你有了最佳的 Q 值，定义最优的策略π*(s)，：当智能体处于状态S时，它应该选择具有最高 Q 值的动作：
我们把这个算法应用到上面的例子中，加深一下理解，首先，我们需要定义MDP：
nan=np.nan # 代表不可能的动作
T = np.array([ # shape=[s, a, s']
[[0.7, 0.3, 0.0], [1.0, 0.0, 0.0], [0.8, 0.2, 0.0]],
[[0.0, 1.0, 0.0], [nan, nan, nan], [0.0, 0.0, 1.0]],
[[nan, nan, nan], [0.8, 0.1, 0.1], [nan, nan, nan]], ])
R = np.array([ # shape=[s, a, s']
[[10., 0.0, 0.0], [0.0, 0.0, 0.0], [0.0, 0.0, 0.0]],
[[10., 0.0, 0.0], [nan, nan, nan], [0.0, 0.0, -50.]],
[[nan, nan, nan], [40., 0.0, 0.0], [nan, nan, nan]], ])
possible_actions = [[0, 1, 2], [0, 2], [1]]
接下来运行Q值迭代函数，如下：
Q = np.full((3, 3), -np.inf) # -inf 对应着不可能的动作
for state, actions in enumerate(possible_actions):
Q[state, actions] = 0.0 # 对所有可能的动作初始化为0.0
learning_rate = 0.01
discount_rate = 0.95
n_iterations = 100
for iteration in range(n_iterations):
Q_prev = Q.copy()
for s in range(3):
for a in possible_actions[s]:
Q[s, a] = np.sum([T[s, a, sp] * (R[s, a, sp] + discount_rate * np.max(Q_prev[sp]))
for sp in range(3)])
最后Q值运行结果，如下：
>>> Q
array([[ 21.89498982, 20.80024033, 16.86353093],
[ 1.11669335, -inf, 1.17573546],
[ -inf, 53.86946068, -inf]])
>>> np.argmax(Q, axis=1) # 每一状态的最优动作
array([0, 2, 1])
这给我们这个 MDP 的最佳策略，当使用 0.95 的衰减率时：在状态S0选择动作a0，在状态S1选择动作a2（通过火焰！）在状态S2中选择动作a1（唯一可能的动作）。有趣的是，如果你把衰减率降低到 0.9，最优的策略改变：在状态S1中，最好的动作变成a0（保持不变；不通过火）。这是有道理的，因为如果你认为现在比未来更重要，那么未来奖励的诱惑是不值得立刻经历痛苦的。
至此，我们今天学习了马尔科夫决策过程的相关知识，下期我们将一起学习下强化学习中的时间差分学习与 Q 学习。希望有些收获，欢迎留言或进社区共同交流，喜欢的话，就点个赞吧，您也可以置顶公众号，第一时间接收最新内容。